﻿// 2-2 矩阵链乘 (20分).cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
/*
date:20200508-20200510 pm 14:00
user:Dongcheng Li
level:9
key:动态规划经典题目
	1.填表的方向是右上
	2.注意以字符串数组存储每一个Mx
	3.从最后一个往回找考虑相同最小花费中括号最向前的情况，找一个最左的第一右括号。
*/
#include <iostream>
#include<stack>
#include<algorithm>
#include<vector>
#include<string>
using namespace std;
vector<string>shchu;


void sdeal(string* zifushuz, int a, int b) {//对字符串加括号处理
	//stack<char>c;

	if (a == b)
	{


	}
	else
	{
		zifushuz[a] = "(" + zifushuz[a];
		zifushuz[b] = zifushuz[b] + ")";
	}



}
void digui(int** mat, int i, int jj, int* shuru, string* zifushuzu)
{
	if (abs(i - jj) <= 1)
	{
		;
	}
	else
	{
		//搜索它的两个分支
		int result;
		int cost = 999999;
		//int i1 = jj;
		int a1, b1, a2, b2;
		int change;
		for (change = i; change != jj; change++)//第一次横纵搜索得到最小花费
		{
			result = mat[i][change] + mat[change + 1][jj] + shuru[i] * shuru[change + 1] * shuru[jj + 1];
			//cout << "cost:" << cost << "result:" << result << endl;
			if (result < cost)
			{
				cost = result;
				a1 = i;
				b1 = change;
				a2 = change + 1;
				b2 = jj;
			}
		}
		for (change = i; change != jj; change++)//第二次横纵搜索用最小花费看看有没有相同括号情况的
		{
			result = mat[i][change] + mat[change + 1][jj] + shuru[i] * shuru[change + 1] * shuru[jj + 1];
			if (result == cost)//最少花费相同的话
			{
				if (b1 > change)//这一次的第一个括号的右括号小于之前的第一个括号的右括号
				{
					a1 = i;
					b1 = change;
					a2 = change + 1;
					b2 = jj;
				}
			}
		}
		sdeal(zifushuzu, a1, b1);
		sdeal(zifushuzu, a2, b2);
		//cout << a1+1 << " " << b1+1 << " " << a2+1 << " " << b2+1 << " " << endl;
		//mat[i][jj] = cost;
		digui(mat, a1, b1, shuru, zifushuzu);
		digui(mat, a2, b2, shuru, zifushuzu);

	}
}
void com(int** mat, int i, int jj, int* shuru) {
	int result;
	int cost = 999999;
	//int i1 = jj;

	for (int change = i; change != jj; change++)
	{
		result = mat[i][change] + mat[change + 1][jj] + shuru[i] * shuru[change + 1] * shuru[jj + 1];
		if (result < cost)
		{
			cost = result;
		}
	}
	mat[i][jj] = cost;
}
int main()
{

	int i, j, n;

	cin >> n;

	//输入矩阵
	int* shuru = new int[n + 1];
	for (i = 0; i < n + 1; i++)
	{
		cin >> shuru[i];
	}
	//初始化字符串数组,如5个矩阵这个就是12345,然而非个位数不会是整体，如((M1(M2(M3(M4(M5M6)))))(((M7M8)M9)M1M0)
	string* zifushuzu = new string[n];
	for (i = 0; i < n; i++)
	{
		zifushuzu[i] = "M" + to_string(i + 1);
	}

	//cout << C << endl;
	//建立矩阵
	int** mat = new int* [n];

	for (i = 0; i < n; i++)
	{
		mat[i] = new int[n];
	}
	//初始化对角线全为0
	for (i = 0; i < n; i++)
	{
		mat[i][i] = 0;
	}

	int edge = n - 1;
	//由于字符串从零开始读而矩阵从一开始读
	int jj;
	for (j = 1; j < n; j++)
	{
		jj = j;
		for (i = 0; jj < n; i++)
		{
			com(mat, i, jj, shuru);//mat[i][jj] = 0;
			jj++;
		}
	}
	cout << mat[0][n - 1] << " ";

	digui(mat, 0, n - 1, shuru, zifushuzu);

	cout << '(';
	for (i = 0; i < n; i++)
	{
		cout << zifushuzu[i];
	}
	cout << ')';
}

